#include <list>
#include <iostream>
#include <unordered_map>

using namespace std;

//class LRUCache {
//private:
//    using NodeT = list<pair<int, int>>::iterator;
//
//public:
//    LRUCache(int capacity)
//        :_capacity(capacity), _size(0)
//    { }
//    
//    int get(int key)
//    {
//        // 不存在
//        if (_map.find(key) == _map.end()) { return -1; }
//        // 1. getValue
//        NodeT& node = _map[key];
//        int value = (*node).second; // 1
//        // 2. update LRU
//        _LRU.push_front(make_pair(key, value));
//        _map[key] = _LRU.begin();
//        _LRU.erase(node);
//        return value;
//    }
//    
//    void put(int key, int value)
//    {
//        // 不存在
//        if (_map.find(key) == _map.end())
//        {
//            _LRU.push_front(make_pair(key, value));
//            _map.insert(make_pair(key, _LRU.begin()));
//            if (++_size > _capacity) {
//                _map.erase(_LRU.end()->second);
//                _LRU.pop_back();
//            }
//        }
//        else
//        {
//            NodeT& node = _map[key];
//            node->second = value;
//            _LRU.push_front(make_pair(key, value));
//            _map[key] = _LRU.begin();
//            _LRU.erase(node);
//        }
//    }
//
//private:
//    int _capacity;
//    int _size;
//    list<pair<int, int>> _LRU;
//    unordered_map<int, NodeT> _map;
//};
//
///**
// * Your LRUCache object will be instantiated and called as such:
// * LRUCache* obj = new LRUCache(capacity);
// * int param_1 = obj->get(key);
// * obj->put(key,value);
// */
class LRUCache {
private:
    using NodeT = list<pair<int, int>>::iterator;

public:
    LRUCache(int capacity)
        :_capacity(capacity), _size(0)
    { }
    
    int get(int key)
    {
        // 不存在
        if (_map.find(key) == _map.end()) { return -1; }
        // 1. getValue
        NodeT& node = _map[key];
        int value = (*node).second; // 1
        // 2. update LRU
        _LRU.push_front(make_pair(key, value));
        _map[key] = _LRU.begin();
        _LRU.erase(node);
        return value;
    }
    
    void put(int key, int value)
    {
        // 不存在
        if (_map.find(key) == _map.end())
        {
            _LRU.push_front(make_pair(key, value));
            _map.insert(make_pair(key, _LRU.begin()));
            if (++_size > _capacity) {
                _map.erase(_LRU.back().first);
                _LRU.pop_back();
                --_size;
            }
        }
        else
        {
            NodeT& node = _map[key];
            node->second = value;
            _LRU.push_front(make_pair(key, value));
            _map[key] = _LRU.begin();
            _LRU.erase(node);
        }
    }

private:
    int _capacity;
    int _size;
    list<pair<int, int>> _LRU;
    unordered_map<int, NodeT> _map;
};

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache* obj = new LRUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */

int main()
{
   LRUCache c(2);
   c.put(1, 1);
   c.put(2, 2);
   cout << c.get(1) << endl;
   c.put(3, 3);
   cout << c.get(2) << endl;
   c.put(4, 4);
   cout << c.get(1) << endl;
   cout << c.get(3) << endl;
   cout << c.get(4) << endl;
   return 0;
}
